package class11;

/**
 * 机器人从起始位置，固定步数，走到目标位置的方式,有多少种？
 * 机器人走路问题
 * path: [1，2，3，4，5，6，7]
 * robot:   s     t
 * 说明：
 * 初始值：start=2, target=4, N=7, times=4
 * start:起始位置
 * target:目标位置
 * N:总共位置数
 * times: 走的步数
 */
public class Code04_robotWay1 {
    public static void main(String[] args) {
        int start = 2, target = 4, N = 7, times = 4;
        int res = way1(start, target, N, times);
        System.out.println("res = " + res);
    }

    public static int way1(int start, int target, int N, int times) {
        // 参数检查
        if (N < 2 || start < 1 || start > N || target < 1 || target > N || times < 1) {
            return -1;
        }
        return process1(start, target, N, times);
    }

    /**
     * cur:机器人当前来的位置
     * rest: 剩余步数
     * target:最终目标
     * N:有哪些位置
     * 返回：机器人从cur出发，走过rest步之后，最终停在aim的方式数，是多少?
     */
    public static int process1(int cur, int target, int N, int rest) {
        // 已经走到结尾，则返回
        if (rest == 0) {// 还剩下0步，则不需要再走
            return cur == target ? 1 : 0; // 如果刚好在target位置，则发现了一种路径
        }
        // rest>0,则还有步数要走
        // 如果走到 1，只能往2方向走
        if (cur == 1) {
            return process1(cur + 1, target, N, rest - 1);
        }
        // 如果走到 N，则只能往 N-1 方向走
        if (cur == N) {
            return process1(cur - 1, target, N, rest - 1);
        }
        // 走到 Mid 位置
        int l = process1(cur - 1, target, N, rest - 1);
        int r = process1(cur + 1, target, N, rest - 1);
        return l + r;

    }
}
